package listbyorder.access001_100.test74;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/4 8:57
 */
public class Solution1 {

    // 简单的二分查找算法
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        // 首先遍历一遍数组
        int m = matrix.length;
        int n = matrix[0].length;
        if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false;
        int row = 0;
        for (; row < m; row++) {
            if (target < matrix[row][0]) {
                break;
            }
        }
        row--;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (matrix[row][mid] < target) {
                l = mid + 1;
            } else if (matrix[row][mid] > target) {
                r = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
